K-Means-Clustering¶
Unüberwachtes Lernen: Clustering¶
Diese Woche liegt der Fokus auf dem Gebiet des unüberwachten Lernens. Wir werden mit Methoden des unüberwachten Lernens (engl. unsupervised learning) wie z. B. Clustering arbeiten. Sie werden (optional) lernen, warum und wie wir die Dimensionalität der Originaldaten reduzieren können und was die wichtigsten Ansätze zur Gruppierung ähnlicher Datenpunkte sind.
Einführung¶
Bislang haben wir Methoden des maschinellen Lernens weitgehend im Kontext des überwachten Lernens vorgestellt. Das heißt, wir haben über Datensätze für maschinelles Lernen gesprochen, die Eingaben $x$ und Ausgaben $y$ haben. Dabei ist das Ziel eines Algorithmus für maschinelles Lernen, zu lernen, wie man $y$ aus $x$ vorhersagen kann. Überwachtes Lernen dominiert traditionell die Mehrheit der praktischen Data-Science-Anwendungen. Aber in dieser Aufgabe werden wir Ansätze diskutieren, die von diesen abweichen. Insbesondere werden wir die Funktion des unüberwachten Lernens betrachten, bei dem uns nicht entsprechende Eingabe/Ausgabe-Paare gegeben sind, sondern bei dem uns nur die Eingaben $x$ gegeben sind. Im Vergleich zu Klassifizierungs- und Regressionsmethoden besteht der Grundsatz darin, dass die Eingabedaten unbeschriftet sind (d. h. es sind keine Labels oder Klassen gegeben). Das wirft natürlich die offensichtliche Frage auf: Wenn uns keine Zielausgabe gegeben wird, was genau sollen wir dann vorhersagen? Und tatsächlich ist die Aufgabe des unüberwachten Lernens auf einer gewissen Ebene mehrdeutig. Die allgemeine Philosophie des unüberwachten Lernens ist jedoch, dass wir eine Art von Struktur in den Daten entdecken wollen und dass der Algorithmus die Struktur der Daten ohne jegliche Hilfe erlernt. Verschiedene Methoden des unüberwachten Lernens arbeiten auf sehr unterschiedliche Weise und entdecken sehr unterschiedliche Arten von Strukturen, aber sie haben alle dieses ähnliche Element.
Clustering¶
In der vorherigen Teilaufgabe haben wir eine Kategorie von Modellen für unüberwachtes maschinelles Lernen untersucht: Die Dimensionalitätsreduktion. Nun werden wir zu einer anderen Klasse von unüberwachten maschinellen Lernmodellen übergehen: Clustering-Algorithmen. Die Hauptidee hinter Clustering ist ziemlich einfach. Clustering-Algorithmen versuchen, aus den Eigenschaften der Daten eine optimale Einteilung oder diskrete Kennzeichnung von Punktgruppen zu lernen. Im Grunde genommen sagen wir uns: "Ich habe hier diese Punkte, und ich denke, dass sie sich in Gruppen organisieren. Es wäre schön, diese Dinge konkreter zu beschreiben und, wenn ein neuer Punkt hinzukommt, ihn der richtigen Gruppe zuzuordnen." Diese allgemeine Idee ermutigt zur Exploration und eröffnet eine Vielzahl von Algorithmen für das Clustering.
Die oben aufgeführten Algorithmen decken nicht alle Clustering-Methoden ab, aber sie sind die am häufigsten verwendeten. Heute werden wir näher auf das K-Means-Clustering eingehen, welches der beliebteste Clustering-Algorithmus ist.
K-means clustering¶
Als erstes Beispiel für einen unüberwachten Lernalgorithmus im Bereich des Clustering betrachten wir den K-Means-Clustering-Algorithmus. Der k-means-Algorithmus ist der beliebteste und gleichzeitig einfachste aller Clustering-Algorithmen. Bevor wir jedoch die formale Definition und Funktion vorstellen, betrachten wir das k-means Clustering aus einem eher visuellen/geometrischen Blickwinkel. Einfach als eine Möglichkeit, Datenpunkte zu clustern. Das Ziel des k-means-Algorithmus ist es, eine Menge von $k$ "Zentren" innerhalb eines unbeschrifteten mehrdimensionalen Datensatzes zu finden (d. h. Punkte $\mu^{(i)} \in \mathbb{R}^n)$, wobei $k$ eine vorher festgelegte Zahl ist. Dies wird durch eine einfache Vorstellung davon erreicht, wie das optimale Clustering aussieht:
- Das "Clusterzentrum" ist das arithmetische Mittel aller zum Cluster gehörenden Punkte.
- Jeder Punkt ist näher an seinem eigenen Clusterzentrum als an anderen Clusterzentren.
Diese beiden Annahmen sind die Grundlage des k-Mittelwertmodells. Auf diese Weise können wir auch jeden Punkt mit seinem nächstgelegenen Zentrum assoziieren und dies als Hinweis darauf verwenden, zu welchem Cluster er gehört. Mit einem k-Means-Modell sind wir also auch in der Lage, neue Datenpunkte zu klassifizieren.
Und so funktioniert es:
Algorithmus: K-means
Gegeben: Datensatz $x^{(i)}, i=1,\ldots,m$
Initialisieren Sie:
Wählen Sie die Anzahl von Clustern $k$, die Sie für optimal halten.
Initialisieren Sie $k$ Punkte als "Zentroide" zufällig im Raum unserer Daten.
$\mu^{(j)} := (x^{(1:m)}), \; j=1,\ldots,k$
Wiederholen Sie den Vorgang bis zur Konvergenz:
3. Ordnen Sie jede Beobachtung ihrem nächstgelegenen Schwerpunkt zu.
$y^{(i)} := argmin_j \|\mu^{(j)} - x^{(i)}\|_2^2, \; i=1,\ldots,m$
4. Aktualisieren Sie die Zentroide auf den Mittelpunkt aller zugewiesenen Beobachtungssätze.
$\displaystyle \mu^{(j)} := \sum_{i=1}^m \frac{x^{(i)} \mathrm{1}\{y^{(i)} = j\}}{\mathrm{1}\{y^{(i)} = j\}}, \;\; j=1,\ldots,k$
5. Wiederholen Sie die Schritte 3 und 4 bis alle Zentroide stabil sind (d. h. sich in Schritt 4 nichts mehr ändert).
Was ist die Verlustfunktion, die wir hier optimieren? Es ist die Summe der Abstände jedes Punktes zu seinem nächstgelegenen Schwerpunkt. Obwohl wir dies hier nicht formal beweisen werden, steht fest, dass der Algorithmus bei jedem Schritt die Verlustfunktion verringert (die Intuition ist, dass jeder Schritt, sowohl die Neuzuordnung von Clustern als auch die Berechnung neuer Zentren, nur den Gesamtverlust verringern kann, und daher wird der Gesamtverlust nur auf diese Weise verringert). Da es außerdem nur eine endliche Anzahl möglicher Clusterungen gibt (natürlich exponentiell groß, aber immer noch endlich), wissen wir, dass der Algorithmus nach einer endlichen Anzahl von Schritten konvergiert (d. h. die Clusterzuweisungen bleiben von einer Iteration zur nächsten konstant, was bedeutet, dass sich die Zentren ebenfalls nicht ändern und der Algorithmus einen Fixpunkt erreicht hat).
In der folgenden Abbildung können Sie sehen, was in jeder Iteration des k-Means-Algorithmus passieren sollte.
Entwickeln einer einfachen k-Means-Implementierung¶
Zunächst einmal müssen wir alle benötigten Bibliotheken und unsere Daten laden. Wir beginnen mit den Standard-Importen: numpy, pyplot, seaborn und scikitlearn-datasets.
# Import numpy, pyplot, datasets
import os
os.environ["OMP_NUM_THREADS"] = '2'
import warnings
warnings.filterwarnings('ignore')
import numpy as np
import pandas as pd
from sklearn import datasets
import seaborn as sns
import matplotlib.pyplot as plt
%matplotlib inline
from IPython import display
import ipywidgets as widgets
# plt.style.use(['seaborn-darkgrid'])
plt.rcParams['figure.figsize'] = (12, 9)
plt.rcParams['font.family'] = 'DejaVu Sans'
Als nächsten Schritt wollen wir einen zweidimensionalen Datensatz erzeugen, der vier verschiedene Blobs enthält. Wir werden den folgenden Satz von 300 Datenpunkten verwenden. Um zu verdeutlichen, dass es sich um einen unüberwachten Algorithmus handelt, lassen wir die Beschriftungen in der Visualisierung weg.
- Initialisieren Sie k Punkte als "Zentroide" zufällig mit RandomState
- Dann wiederholen Sie die Schrittzuweisung, aktualisieren die Zentroide und prüfen die Konvergenz
# use the following import to simplify the implementation
from sklearn.metrics import pairwise_distances_argmin,pairwise_distances
# 1. Select the number of clusters: This has to be done before the function is called
# rseed is the seed for generation of random numbers
max_iter=1000
tol=1e-4
def find_clusters(X: np.ndarray, n_clusters: int, rseed: int):
# 2. Initialize k points as "centroids" randomly
# Please initialize the random number generator with specified random state
# STUDENT CODE HERE
rng = np.random.RandomState(rseed)
centers = X[rng.choice(len(X), n_clusters, replace=False)]#np.zeros((n_clusters,2))
for i in range(max_iter):
# Zuordnung der Datenpunkte zu den nächsten Zentren
labels= pairwise_distances_argmin(X, centers)
# Neue Zentren berechnen
new_centers = np.array([X[labels == j].mean(axis=0) for j in range(n_clusters)])
# Überprüfung auf Konvergenz
shift = np.linalg.norm(new_centers - centers)
if shift < tol:
print(f"Konvergenz nach {i} Iterationen erreicht.")
break
centers = new_centers
# STUDENT CODE until HERE
# return the cluster centers and the labels
return centers, labels
Analysieren von Blob-Daten¶
from sklearn.datasets import make_blobs
RANDOM_STATE = 4
n_cluster=4
# STUDENT CODE HERE
X_blob, y_blob = make_blobs(
n_samples=300, centers=n_cluster,cluster_std=0.70, random_state=RANDOM_STATE, shuffle=True
)
centers, labels_blob=find_clusters(X_blob,n_cluster,RANDOM_STATE)
print(centers)
plt.scatter(X_blob[:, 0],X_blob[:, 1],c=labels_blob, cmap='viridis', s=50)
plt.scatter(centers[:,0],centers[:,1],marker='x',color="red",s=100)
plt.show()
# STUDENT CODE until HERE
Konvergenz nach 9 Iterationen erreicht. [[ 9.6290191 -9.800363 ] [ 9.49378092 2.64630988] [ 3.87820608 -5.33258785] [ 4.3092231 -6.48958445]]
Analysieren eines weiteren synthetischen Datensatzes¶
Wir haben unseren ersten Datensatz mit der Funktion make_blobs erzeugt. Um ein besseres Gefühl für die Eigenschaften von k-Means zu bekommen, wollen wir die Ergebnisse mit einem weiteren Datensatz analysieren. Wir importieren die Funktion make_moons aus sklearn datasets und erzeugen einen weiteren Datensatz, bestehend aus 300 Datenpunkte. Der Rauschwert $0.05$, um eine gewisse Abweichung in unserem Datensatz einzubeziehen.
from sklearn.datasets import make_moons
X_moon, y_moon = make_moons(300, noise=.05, random_state=RANDOM_STATE)
# STUDENT CODE HERE
centers, labels=find_clusters(X_moon,n_clusters=4,rseed=1)
plt.scatter(X_moon[:, 0],X_moon[:, 1],c=labels, cmap='viridis', s=50)
plt.scatter(centers[:,0],centers[:,1],marker='x',color="red",s=100)
plt.show()
# STUDENT CODE until HERE
Konvergenz nach 8 Iterationen erreicht.
Ob das Ergebnis aussagekräftig ist, ist eine Frage, die schwer zu beantworten ist. In den folgenden Aufgaben werden wir verschiedene Ansätze kennenlernen.
Evaluieren eines Clusterings¶
Wie bereits zu Beginn der heutigen Session erwähnt, ist die Auswertung von Clustering-Ergebnissen schwierig. Bei den synthetischen Datensätzen, die wir oben erzeugt haben, haben wir gelabelte Daten, da die Blobs / Monde als vorgegebene Klassen (Cluster) gesehen werden können. Wir können die Übereinstimmung unserer Clustering-Ergebnisse mit dem gegebenen Label überprüfen. Aber im Allgemeinen verwenden wir unüberwachte Methoden, wenn wir keine Labels für unsere Daten haben. Was können wir also tun, wenn es kein Label zum Überprüfen gibt? Wir sind nur dann in der Lage, unser Clustering zu evaluieren, wenn wir ein Maß für die Qualität eines Clusterns definieren können. Die Auswertung eines Clustering gibt Aufschluss darüber, nach wie vielen Clustern gesucht werden soll. Es gibt interne und externe Gütemetriken. Externe Metriken verwenden die Informationen über die bekannte wahre Aufteilung (wir haben Labels), während interne Metriken keine externen Informationen verwenden und die Güte von Clustern nur auf Basis der Ausgangsdaten bewerten. Die optimale Anzahl von Clustern wird normalerweise in Bezug auf einige interne Metriken definiert.
Verwenden von gegebenen Labels in einer einfachen Tabelle¶
Zunächst verwenden wir die gegebenen Informationen der Labels. Zu diesem Zweck können wir die cross-tabulation verwenden, die eine Methode zur quantitativen Analyse der Beziehung zwischen mehreren Variablen bereitstellt. In unserem Fall sind die beiden Variablen unsere Labels und die geschätzten Cluster.
- Abrufen der Listen der Clustering-Ergebnisse für den Blob-Datensatz und die Label Daten
- Verwenden Sie die Bibliothek *pandas*, um die cross-tabulation durchzuführen.
- Setzen Sie den Index und die Spalten der Tabelle richtig. Der Index sollte den echten / realen Cluster anzeigen, und die Spalte sollte beschreiben, welchem Cluster die Punkte zugeordnet wurden.
# STUDENT CODE HERE
pd.crosstab(y_blob,labels_blob)
# STUDENT CODE until HERE
| col_0 | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| row_0 | ||||
| 0 | 0 | 75 | 0 | 0 |
| 1 | 0 | 75 | 0 | 0 |
| 2 | 0 | 0 | 55 | 20 |
| 3 | 75 | 0 | 0 | 0 |
Messung der Clustering-Qualität ohne Etiketten: Silhouetten-Koeffizient¶
Im Gegensatz zu der oben beschriebenen Metrik impliziert der Silhouettenkoeffizient nicht das Wissen über die wahren Labels der Objekte. Er ermöglicht es uns, die Qualität des Clustering nur anhand der anfänglichen, nicht gelabelten Datenpunkte und des Clustering-Ergebnisses zu schätzen. Zu Beginn wird für jede Beobachtung der Silhouettenkoeffizient berechnet. Sei $a$ der Mittelwert des Abstands eines Objekts zu anderen Objekten innerhalb eines Clusters und $b$ der mittlere Abstand eines Objekts zu Objekten des nächstgelegenen Clusters (der sich von dem unterscheidet, zu dem das Objekt gehört). Dann sei das Silhouettenmaß für dieses Objekt $$s = \frac{b - a}{\max(a, b)}.$$
Die Silhouette eines Datenpunktes ist ein Mittelwert der Silhouettenwerte aus diesem Datenpunkt. Der Silhouettenabstand zeigt also an, wie stark sich der Abstand zwischen den Objekten der gleichen Klasse vom mittleren Abstand zwischen den Objekten aus verschiedenen Clustern unterscheidet. Dieser Koeffizient nimmt Werte im Bereich $[-1, 1]$ an. Werte nahe bei -1 entsprechen schlechten Clustering-Ergebnissen, während Werte näher bei 1 dichten, gut definierten Clustern entsprechen. Je höher also der Silhouettenwert ist, desto besser sind die Ergebnisse des Clusterns.
# STUDENT CODE HERE
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
silhouette_score(X_blob, labels_blob)
# STUDENT CODE until HERE
0.6739661787526845
Clustering mit scikit-learn Implementation¶
Nachdem wir unsere eigene Implementierung von K-means analysiert haben, können wir nun die von scikit-learn vorgegebene Implementierung verwenden. Das eingebaute K-Means verwendet standardmäßig die Initialisierung von KMeans++. Weitere Details zu dieser Initialisierungsprozedur finden Sie im Anhang. Um konsistente und reproduzierbare Ergebnisse zu erhalten, müssen wir nur den Zufallszustand angeben, wie wir es in unserer eigenen Version getan haben. Ein Vorteil von scikit-learn ist, dass wir mit einer eingebauten Funktion direkt Cluster-Labels für neue Datenpunkte schätzen können. Dabei werden die neuen Datenpunkten den vorhandenen Clustern zugeordnet. Da sich k-means den Mittelwert jedes Clusters (die "Zentroide") merkt, ist es möglich, zu jeder neuen Probe den nächstgelegenen Zentroid zu finden und das entsprechende Label zuzuweisen.
Nun beginnen wir, die Ergebnisse von oben mit scikit-learn zu reproduzieren. Wir werden auswerten, ob wir im Blob-Datensatz die gleichen Cluster wie zuvor finden.
- Importieren Sie KMeans aus sklearn.cluster.
- Erstellen Sie mit
KMeans()eine KMeans-Instanz, um die richtige Anzahl von Clustern zu finden. Um die Anzahl der Cluster anzugeben, verwenden Sie das Schlüsselwort-Argument n_clusters. - Verwenden Sie die Methode
.fit()von model, um das Modell an das Array von Punkten anzupassen. - Verwenden Sie die Methode
.predict()des Modells, um die Cluster-Labels unseres Datensatzes vorherzusagen, und weisen Sie das Ergebnis den Labels zu
# STUDENT CODE HERE
from sklearn.cluster import KMeans
kmeans=KMeans(n_clusters=4,random_state=4).fit(X_blob)
labels_blob=kmeans.predict(X_blob)
# STUDENT CODE until HERE
#plotting is given
plt.scatter(X_blob[:, 0], X_blob[:, 1], c=labels_blob,
s=50, cmap='viridis')
plt.show()
Wählen Sie einen geeigneten Wert für $k$¶
Eine offensichtliche Frage, die sich bei der Verwendung von K-Means stellt, ist: Wie wählt man die Hyperparameter für den Algorithmus, wie z. B. die Anzahl der Zentren $k$? Im Allgemeinen haben wir nur die Datenpunkte und den Cluster, dem sie zugeordnet sind. Nun brauchen wir ebenso Metriken, die von den Datenpunkten abhängen, um den perfekten Wert für $k$ auszuwählen.
Verwendung des Silhouette-Koeffizienten¶
Eine Möglichkeit ist die Verwendung des Silhouettenkoeffizienten, den wir oben eingeführt haben. Mit Hilfe der Silhouette können wir die optimale Anzahl von Clustern $k$ identifizieren (wenn wir sie nicht schon aus den Daten kennen), indem wir die Anzahl von Clustern nehmen, die den Silhouettenkoeffizienten maximiert.
def calculate_k_silhouette(X:np.ndarray, k_min:int, k_max:int):
# STUDENT CODE HERE
scores=[]
for k in range(k_min,k_max+1):
kmeans=KMeans(n_clusters=k,random_state=4).fit(X)
labels_blob=kmeans.predict(X)
scores.append(silhouette_score(X, labels_blob))
ks=np.arange(k_min,k_max+1)
# STUDENT CODE until HERE
return ks, scores
#set random state
RANDOM_STATE = 42
# call your function with a suitable range for k
# STUDENT CODE HERE
ks,silhouette_scores=calculate_k_silhouette(X_blob,2,10)
# STUDENT CODE until HERE
# Plot ks vs silhouette coefficient
plt.plot(ks, silhouette_scores, '-o')
plt.xlabel('number of clusters, k')
plt.ylabel('Silhouette Score')
plt.xticks(ks)
plt.show()
Verwendung der Ellenbogenmethode¶
Ein gutes Clustering hat enge Cluster und die Datenpunkte in jedem Cluster sind zusammengeballt. Daher können wir die Streuung jedes Clusters bewerten, wobei eine geringere Streuung besser ist. K-means optimiert von Natur aus die Summe der quadratischen Abstände zwischen den Beobachtungen und ihren Zentren. Dies ist die Verlustfunktion für den k-Means-Algorithmus.
$$ J(C) = \sum_{k=1}^K\sum_{i~\in~C_k} ||x_i - \mu_k|| \rightarrow \min\limits_C,$$Wir können die Verlustfunktion als Qualitätsmaß verwenden. Das scheint vernünftig zu sein -- wir wollen, dass unsere Beobachtungen so nah wie möglich an ihren Zentren liegen. Bewerten Sie nun, was das Qualitätsmaß über die Verlustfunktion für verschiedene Werte von $k$ anzeigt!
- Definieren Sie die Liste der k-Werte
- Führen Sie für jeden der Werte von k die folgenden Schritte aus:
- 1. Anpassen eines K-Means-Modells an die gegebenen Datenproben mit k Clustern
- 2. Berechnen Sie den Verlust
def calculate_k_loss(X:np.ndarray, k_min:int, k_max:int):
# STUDENT CODE HERE
ks=np.arange(k_min,k_max+1)
losses=[]
for k in range(k_min,k_max+1):
kmeans=KMeans(n_clusters=k,random_state=4).fit(X)
labels_blob=kmeans.predict(X)
sum_dist=0
for i in range(k):
center=kmeans.cluster_centers_[i,:]
dist=pairwise_distances([center],X_blob[labels_blob==i])
sum_dist=sum_dist+np.sum(dist)
losses.append(sum_dist)
# STUDENT CODE until HERE
return ks, losses
#set random state
RANDOM_STATE = 42
# call your function with a suitable range for k
# STUDENT CODE HERE
ks,losses=calculate_k_loss(X_blob,2, 20)
# STUDENT CODE until HERE
# Plot ks vs inertias
plt.plot(ks, losses, '-o')
plt.xlabel('number of clusters, k')
plt.ylabel('$ J(C)$')
plt.xticks(ks)
plt.show()
Zusammenfassend lässt sich sagen, dass die Auswahl der Anzahl von Clustern typischerweise eine wage Kunst ist und es sehr schwierig ist, aus der Ausführung von k-means etwas über die "wirkliche" Anzahl von Clustern in den Daten abzuleiten (tatsächlich sollten Sie dies niemals versuchen).
Mean-Shift Clustering¶
Mean-Shift Clustering ist ein Schwerpunkt basierter Algorithmus. Hierbei wird der Schwerpunkt über das relative Auftreten der Datenpunkte definiert. Dies bedeutet in der Praxis, das kreisförige Strukturen gesucht werden, die so im Bild liegen, dass möglichst viele Datenpunkte in der Struktur liegen. Kritisch hierbei ist die Größe der Struktur, die auch als Bandwith bezeichnet wird. In der Praxis werden ganz viele solcher Strukturen, die zufällig im Bild verteilt werden, berechnet und bei Überlappung verschmolzen. Dies hat den Vorteil, dass im Gegensatz zu k-Means die Anzahl an Clustern nicht vorgegeben werden muss. Dafür ist der Algorithmus langsamer.
Gegeben sind nun die bereits bekannten Blob-Daten:
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
RANDOM_STATE = 42
X_blob, y_blob = make_blobs(
n_samples=300, centers=4,cluster_std=0.60, random_state=RANDOM_STATE, shuffle=True
)
plt.figure(figsize=(15,10))
plt.scatter(X_blob[:, 0],X_blob[:, 1], s=50)
plt.show()
sklearn um die Daten mittels Mean-Shift Clustering zu Clustern und speichern Sie das Ergebnis in einer Variablen mit dem Namen predicted_labels.
Hinweis: Verweden Sie sklearn.cluster.MeanShift und eine bandwidth von 4.
# STUDENT CODE HERE
from sklearn.cluster import MeanShift
result=MeanShift(bandwidth=40).fit(X_blob)
predicted_labels=result.labels_
# STUDENT CODE until HERE
plt.figure(figsize=(15,10))
plt.scatter(
X_blob[:, 0], X_blob[:, 1], c=predicted_labels
)
plt.show()
bandwith auf 0.4 bzw. 40 statt 4 setzten
DBSCAN¶
Auch DBSCAN arbeitet dichtebasiert. Diesem Verfahren liegt die Annahme zugrunde, dass Cluster Orte hoher Dichte sind, die durch Bereiche niedriger Dichte voneinander getrennt werden. Hierzu werden sogenannte Core Samples bestimmt. Hierbei handelt es sich um Datenpunkte, die in einem sehr dichten Bereich liegen. Somit wird die Position eines Clusters von seinen Core Samples bestimmt. Daraus folgt ebenso, dass die Core Samples eines Clusters nah beieinander liegen. Anschließend werden die verbleibenden nicht - Core Samples dem naheliegensten Cluster zugewiesen, sofern diese nicht zu weit entfernt von den Core Samples liegen. Somit kann es Datenpunkte geben, die keinem Cluster zugeordnet werden. DBSCAN besitzt i.d.R. zwei Parameter, nämlich:
1.) Die Mindestanzahl an Datenpunkte für einen Cluster sowie
2.) Epsilon, welches welches den maximalen Abstand zwischen zwei Datenpunkten, die im gleichen Cluster liegen, angibt.
Gegeben seien wieder die bekannten Blob-Daten:
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
RANDOM_STATE = 42
X_blob, y_blob = make_blobs(
n_samples=300, centers=4,cluster_std=0.60, random_state=RANDOM_STATE, shuffle=True
)
plt.figure(figsize=(15,10))
plt.scatter(X_blob[:, 0],X_blob[:, 1], s=50)
plt.show()
sklearn um die Daten mittels DBSCAN zu Clustern und speichern Sie das Ergebnis in einer Variablen mit dem Namen predicted_labels.
Hinweis: Verweden Sie sklearn.cluster.DBSCAN, mit eps=0.5 und min_samples=5
# STUDENT CODE HERE
from sklearn.cluster import DBSCAN
result=DBSCAN(eps=0.5,min_samples=1).fit(X_blob)
predicted_labels=result.labels_
# STUDENT CODE until HERE
plt.figure(figsize=(15,10))
plt.scatter(
X_blob[:, 0], X_blob[:, 1], c=predicted_labels
)
plt.show()
print('Number of classes: {}'.format(len(list(filter(lambda x: x != -1 , set(predicted_labels))))))
Number of classes: 11
min_samples auf 1 bzw. 10 statt 5 setzen?
eps auf 0.1 bzw. 1.0 statt 0.5 setzen?
HDBSCAN¶
HDBSCAN ist eine Erweiterung DBSCAN, bei dem, stark vereinfacht, die Berechnung von Epsilon sowie die Anzahl an Datenpunkten pro Cluster, auf Kosten der Laufzeit, automatisiert wurde.
Gegeben sei der bekannte Blob-Datensatz:
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
RANDOM_STATE = 42
X_blob, y_blob = make_blobs(
n_samples=300, centers=4,cluster_std=0.60, random_state=RANDOM_STATE, shuffle=True
)
plt.figure(figsize=(15,10))
plt.scatter(X_blob[:, 0],X_blob[:, 1], s=50)
plt.show()
hdbscan mit den Parametern min_cluster_size=5 (minimale Anzahl an Datenpunkten die einen Cluster bilden) sowie min_samples=None (Steuert die Anzahl an DAtenpunkten, die keiner Klasse zugeordnet werden können), um die Daten mittels HDBSCAN zu Clustern und speichern Sie das Ergebnis in einer Variablen mit dem Namen predicted_labels.
Hinweis: Verweden Sie hdbscan.HDBSCAN, welches das gleiche Interface wie die die vorherigen Methoden besitzt.
Hinweis 2: Sollten Sie die Aufgabe lokal ausführen, müssen Sie die Bibliothek hdbscan installieren. Dies können Sie in der Anaconda Promt mittels "conda install -c conda-forge hdbscan" durchführen.
from sklearn.cluster import HDBSCAN
# STUDENT CODE HERE
result=HDBSCAN(min_cluster_size=5,min_samples=100).fit(X_blob)
predicted_labels=result.labels_
# STUDENT CODE until HERE
plt.figure(figsize=(15,10))
plt.scatter(
X_blob[:, 0], X_blob[:, 1], c=predicted_labels
)
plt.show()
print('Number of classes: {}'.format(len(list(filter(lambda x: x != -1 , set(predicted_labels))))))
Number of classes: 0
min_cluster_size auf 10 bzw. 100 statt 5 setzen?
min_samples auf 1, 10 bzw. 100 statt 5 setzen?
Praktische Anwendung - Bildkomprimierung¶
Im folgenden sollen die genannten Algorithmen praktisch an einem Beispielbild ausprobiert werden, d.h. wir werden im folgenden die Bildkompression mittels Clustering betrachten.
Das Ursprungsbild sieht wie folgt aus:
# NICHT ÄNDERN
from skimage import io
import os
import matplotlib.pyplot as plt
path_to_image = os.path.join('images', 'Lamas_0.png')
image = io.imread(path_to_image)
plt.figure(figsize=(15,10))
plt.imshow(image)
plt.show()
Nun wird das gezeigte Bild mittels KMeans komprimiert.
Achtung: Die Berechnung kann etwas Zeit in anspruch nehmen.
from skimage import img_as_float
from sklearn.cluster import KMeans
import numpy as np
# Bild-Dimensionen
rows = image.shape[0]
cols = image.shape[1]
# Bilddimension ändern
image_reshaped = image.reshape(rows*cols, 4)
# k-means
model = KMeans(n_clusters=10)
model.fit(image_reshaped)
# neues Bild erzeugen
compressed_image = model.cluster_centers_[model.labels_]
compressed_image = np.clip(compressed_image.astype('uint8'), 0, 255)
# In Ursprungsdimension konvertieren
compressed_image = compressed_image.reshape(rows, cols, 4)
plt.figure(figsize=(15,10))
plt.imshow(compressed_image)
plt.show()
